package com.zecan.primAlgorithm;

import java.util.Arrays;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/13
 * \* Time: 14:42
 * \* Description:
 * \
 */
public class Prim {
    public static void main(String[] args) {
        char[] data = {'A','B','C','D','E','F','G'};
        int vertexNum = data.length;
        MGraph graph = new MGraph(vertexNum);
        int[][] weight = {{10000,5,7,10000,10000,10000,2},{7,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},{10000,10000,8,10000,10000,5,4},
                {10000,9,10000,10000,10000,5,10000},{10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}};
        minTree minTree = new minTree();
        minTree.createGraph(graph,vertexNum,weight,data);
        minTree.showGraph(graph);
        minTree.prim(graph,1);
    }
}
/*
 * @Author Lints
 * @Date
 * @Description 最小生成树的类
 * @Since version-1.0
 */
class minTree {
    /**
     * 
     * @param graph 将要创造的图
     * @param vertexNum 结点的个数
     * @param weight 包含边的信息
     * @param data 包含结点的信息
     * @author 
     * @creed: Talk is cheap,show me the code
     * @date  
     */
    public void  createGraph(MGraph graph,int vertexNum, int[][] weight,char[] data) {
        int i,j;
        for(i = 0 ; i < vertexNum ; i++) {
            graph.data[i] = data[i];
            for(j = 0 ; j <vertexNum ; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }
    public void showGraph(MGraph graph) {
        for (int[] arr: graph.weight
             ) {
            System.out.println(Arrays.toString(arr));
        }
    }
    /**
     * 使用prim算法生成最小生成树
     * @param graph 所要进行prim算法的图
     * @param v 从那个顶点开始
     * @return void
     * @author 
     * @creed: Talk is cheap,show me the code
     * @date  2021年10月13日15:26:04
     */
    public  void prim(MGraph graph, int v) {
        int[] visited = new int[graph.data.length]; // 此数组的作用是判断当前顶点是否被访问过
        // 将第v个顶点设置为访问过
        visited[v] = 1; // 1 --> 已访问  0-->未访问
        int access = 0; // 指向已访问的顶点的下标
        int noAccess = 0; //指向未访问顶点的下标
        int minData = 10000;// 指向最小边的权值 初始为10000
        int i, j , k;
        int maxWay = 0;
        // 此循环的作用是 有 n 个 顶点的图 所构成的最小生成树为 n - 1 所以需要循环n-1次
        for(i = 1 ; i < graph.vertexNum; i++) {
            for(j = 0 ; j < graph.vertexNum; j++) { //此循环的作用是循环已经访问过的节点
                for (k = 0 ; k < graph.vertexNum; k++) { // 此循环的作用是循环未访问过的顶点
                    // 当顶点j 已经是访问过的(以顶点j出发查找最小边) 和 顶点k 未访问过 且 weight[j][k]的权值小于当前最小的边的权值
                    if(visited[j] == 1 &&  visited[k] == 0 && graph.weight[j][k] < minData) {
                        minData = graph.weight[j][k];
                        access = j; // 记录当前添加的顶点
                        noAccess = k;
                    }
                }
            }
            maxWay += graph.weight[access][noAccess];
            // 当循环退出后 此时已经找到了一条最小权值的边
            System.out.println("<边 [" + graph.data[access] + "->" + graph.data[noAccess] +
                    "] 权值 = " + graph.weight[access][noAccess]);
            minData = 10000; // 将指向最小边的权值初始化
            visited[noAccess] = 1; // 此时将循环退出后找到的的顶点设置为已访问
        }

        System.out.println("最小生成树的路径为 " + maxWay);
    }
}
class MGraph{
    int vertexNum; // 结点的个数
    int[][] weight; // 邻接矩阵的数组
    char[] data; // 标识顶点的数组

    public MGraph(int vertexNum) {
        this.vertexNum = vertexNum;
        this.weight = new int[vertexNum][vertexNum];
        this.data = new char[vertexNum];
    }
}
